
from copy import copy

def merge(d1, d2):      # match-collect的匹配结果merge
    d = {k: copy(v) for k, v in d1.items()}
    for k, v in d2.items():
        if isinstance(v, list):
            if k in d:
                d[k].extend(v)
            else:
                d[k] = []
                d[k].extend(v)
        else:
            if k in d:
                print("合并错误", d, k, v)
                assert False, [k, d[k]]
            else:
                d[k] = v
    return d


class Pat:
    def __init__(self, a, b=None):
        if b is None:
            assert type(a) is not Pat
            self.v = a
            self.name = None
        else:
            assert isinstance(a, (str, type(None)))
            assert type(b) is not Pat
            self.v = b
            self.name = a
        assert type(self.v) is not Pat

    def __eq__(self, other):
        if not isinstance(other, Pat):
            return False
        if self.name is not None:
            return self.name == other.name
        else:
            return self is other

    def __repr__(self):
        if self.name is None:
            return 'p@'+repr(self.v)
        else:
            return f'<{self.name}>'

class Farg:
    def __init__(self, name, pat, ctype):
        assert ctype in ['uni', 'list']
        self.name = name
        if isinstance(pat, Pat):
            self.pat = pat
        else:
            assert type(pat) is not Farg
            self.pat = Pat(pat)
        self.ctype = ctype
    def __repr__(self):
        if self.ctype == 'uni':
            return f'{repr(self.pat)}/{self.name}/{self.ctype}'
        else:
            return f'[{repr(self.pat)}]/{self.name}/{self.ctype}'


class Fargh:  # Farg help obj
    def __init__(self, ctype):
        self.ctype = ctype

    def __rsub__(self, p):
        return Fargh2(p, self.ctype)


class Fargh2:  # Farg help obj
    def __init__(self, p, ctype):
        self.p = p
        self.ctype = ctype

    def __sub__(self, name):
        return Farg(name, self.p, self.ctype)

cl = Fargh("list")
cu = Fargh("uni")



def t4(pat):
    if isinstance(pat, Pat):
        name = None
        co = None
        patn = pat
        pat = pat.v
    elif isinstance(pat, Farg):
        assert isinstance(pat.pat, Pat)
        name = pat.name
        co = pat.ctype
        patn = pat.pat
        pat = patn.v
    else:
        raise TypeError()
    return name, co, patn, pat

def match_collect(x, pat) -> (bool, "pat", "tree", dict):
    name, co, patn, pat = t4(pat)

    if isinstance(pat, listb):
        if not isinstance(x, tuple):
            return False, None
        if len(pat) != len(x):
            return False, None
        else:
            acc = {}
            lili = None
            for xi, pi in zip(x, pat):
                namei, coi, patni, pati = t4(pi)
                b, d2 = match_collect(xi, pi)
                if not b:
                    # ~ print("子项", xi,"不匹配", pi)
                    return False, None
                else:
                    #print("子项", xi,"匹配", pi, "收集", d2)
                    acc = merge(acc, d2)
                    if name is not None and name == namei:
                        assert lili is None
                        lili = namei
            else:
                #print("递归情况：", lili)
                if co == None:
                    if lili is None:
                        return True, acc
                    else:
                        assert False, '?'
                elif co == "list":
                    if lili is None:
                        return True, {name: [(patn, acc)]}
                    else:   # 如果递归，则不增加字典嵌套层级；uni匹配则增加字典嵌套层级
                        thing = acc[name]
                        del acc[name]
                        return True, {name: [(patn, acc)] + thing}
                elif co == "uni":
                    return True, {name: (patn, acc)}
                else:
                    raise Exception("unknown collect mode")


    elif isinstance(pat, list): # 列表子项的收集名，替换为整体的收集名
        if len(pat) == 0:
            return False, None
        else:
            for pi in pat: #两层连续列表有bug
                namei, coi, patni, pati = t4(pi)
                if coi is None:         # 如果列表的项没有收集标志，那么会使用整个列表的收集标志
                    coi = co
                if namei is None:
                    namei = name
                elif name is not None:
                    prefix = name+'.'
                    namei += prefix
                if coi:
                  pi = Farg(namei, patni, coi)
                else:
                  pi = patni
                b, d2 = match_collect(x, pi)
                if b:
                    return b, d2
            else:
                return False, None

    elif isinstance(pat, Farg): # 单项式
        b, d2 = match_collect(x, pat)
        if b:
                return b, d2
        else:
            return False, None

    elif isinstance(pat, type) or x == pat:
        if isinstance(pat, type):
            b = isinstance(x, pat)
        else:
            b = True
        if b:
            if co == None:
                return True, {}
            elif co == "list":
                return True, {name: [(patn, x)]}
            elif co == "uni":
                return True, {name: (patn, x)}
            else:
                assert False
        else:
            return False, None
    else:
        return False, None


class listb(list):pass

def reo(x):     # 此函数不能处理递归，所以不应手动调用该函数，只能对一个大表进行link
    if isinstance(x, tuple):
        return Pat(listb(reo(xi) for xi in x))
    elif isinstance(x, list):
        return Pat(list(reo(xi) for xi in x))
    elif isinstance(x, Pat):
        if not isinstance(x.v, Farg):
            return Pat(x.name, reo(x.v).v)
        else:       # 单项式，仅包含一次分配的Patten
            return Pat(x.name, reo(x.v))
    elif isinstance(x, Farg):
        return Farg(x.name, reo(x.pat), x.ctype)
    else:
        return Pat(x)

def re(d):      # 正规化，把字面值都补全成Pattern
    for k in d:
        d[k] = reo(d[k])

def rep(x, d): #元组递归是无法处理的，只有列表, Pat,Farg可以修改内容
    if isinstance(x, Pat):
        if isinstance(x.v, (listb, list)):
            for xi in x.v:
                rep(xi, d)
        elif isinstance(x.v, str):
            if x.v in d:
                that = d[x.v]
                x.v = that.v
                x.name = that.name
        elif isinstance(x.v, Farg):     # 单项式
            rep(x.v, d)
    elif isinstance(x, Farg):
        rep(x.pat, d)
    else:
        raise TypeError(repr(x))

def link(d):
    re(d)
    for x in d.values():
        rep(x, d)

#警告：单个组内只能出现一个cl


if __name__ == "__main__":
    ast = \
    ("=", 5,
        ("=", 4,
            ("=", 3,
                2
            )
        )
    )

    pats = {
           '$eq': Pat('Seq', '='),
           '$int': Pat('Pint', int),
        "$as": Pat('Pas', ('$eq', '$int'-cl-"a", ['$int'-cu-'b', "$as"])),
        #"$as": Pat('Pas', ('$eq', '$int'-cu-"a", ['$int', "$as"]-cl-'b'))
        #"$as": Pat('Pas', ('$eq', '$int'-cu-"a", ['$int', "$as"]-cu-'b'))
    }

    link(pats)
    print(pats)
    print(pats['$as'].v)
    print(match_collect(ast, pats["$as"]))




    print('#' * 20)

    ast = \
    ("elif", "d == 1",
        ("elif", "c == 1",
            ("elif", "b == 1",
                ("if", "a == 1")
            )
        )
    )

    pats = {
        "$if": Pat('Pif', ("if",  object-cu-"ifx")),
        "$elif": Pat('Pelif', ("elif", object-cl-"elifx", ["$if", "$elif"]))
    }

    link(pats)

    print(pats)
    print(match_collect(ast, pats["$elif"]))







